#!/usr/bin/python
# -*- coding:UTF-8 -*-

from random import random, randint, choice
from copy import deepcopy
from math import log


# 一个封装类，对应于“函数”节点上包括了函数名称、函数本身,以及该函数接受的参数个数
class fwrapper:
    def __init__(self, function, childcount, name):
        self.function = function
        self.childcount = childcount
        self.name = name


# 对应于函数型节点(即带子节点的节点)。我们以一个fwrapper类对其进行初始化.当evaluate被调用时,
# 我们会对各个子节点进行求值运算,然后再将函数本身应用于求得的结果
class node:
    def __init__(self, fw, children):
        self.function = fw.function
        self.name = fw.name
        self.children = children

    def evaluate(self, inp):
        results = [n.evaluate(inp) for n in self.children]
        return self.function(results)

    def display(self, indent=0):
        print(' ' * indent) + self.name
        for c in self.children:
            c.display(indent + 1)


# 这个类对应的节点只返回传递给程序的某个参数。其evaluate方法返回的是idx指定的参数
class paramnode:
    def __init__(self, idx):
        self.idx = idx

    def evaluate(self, inp):
        return inp[self.idx]

    def display(self, indent=0):
        print
        '%sp%d' % (' ' * indent, self.idx)


# 返回常量值的节点.其evaluate方法仅返回该类被初始化时所传入的值
class constnode:
    def __init__(self, v):
        self.v = v

    def evaluate(self, inp):
        return self.v

    def display(self, indent=0):
        print
        '%s%d' % (' ' * indent, self.v)


addw = fwrapper(lambda l: l[0] + l[1], 2, 'add')
subw = fwrapper(lambda l: l[0] - l[1], 2, 'subtract')
mulw = fwrapper(lambda l: l[0] * l[1], 2, 'multiply')


def iffunc(l):
    if l[0] > 0:
        return l[1]
    else:
        return l[2]


ifw = fwrapper(iffunc, 3, 'if')


def isgreater(l):
    if l[0] > l[1]:
        return 1
    else:
        return 0


gtw = fwrapper(isgreater, 2, 'isgreater')

flist = [addw, mulw, ifw, gtw, subw]


def exampletree():
    return node(ifw, [
        node(gtw, [paramnode(0), constnode(3)]),
        node(addw, [paramnode(1), constnode(5)]),
        node(subw, [paramnode(1), constnode(2)])
    ]
                )


def makerandomtree(pc, maxdepth=4, fpr=0.5, ppr=0.6):
    if random() < fpr and maxdepth > 0:
        f = choice(flist)
        children = [makerandomtree(pc, maxdepth - 1, fpr, ppr) for i in range(f.childcount)]
        return node(f, children)
    elif random() < ppr:
        return paramnode(randint(0, pc - 1))
    else:
        return constnode(randint(0, 10))


# ===============实现隐性函数的构造===========
def hiddenfunction(x, y):
    return x ** 2 + 2 * y + 3 * x + 5


# 构造数据集
def buildhiddenset():
    rows = []
    for i in range(200):
        x = randint(0, 40)
        y = randint(0, 40)
        rows.append([x, y, hiddenfunction(x, y)])
    return rows


# 衡量题解的优劣程度
def scorefunction(tree, s):
    dif = 0
    for data in s:
        v = tree.evaluate([data[0], data[1]])
        dif += abs(v - data[2])
    return dif


# 遗传变异
# 一个树状程序可以有多种修改方式--我们可以改变节点上的函数,也可以改变节点的分支
# 一种变异方式：删除旧的分支,也可以增加新的分支
# 另一种变异的方式：利用一棵全新的树来替换某一子树,变异的次数不宜过多，
# 我们可以为任何须要进行修改的节点定义一个相对较小的概率。从树的根结点开始，
# 如果每次生成的随机数小于该概率值,就以如上所述的某种方式对节点进行变异;否则,就再次对子节点进行测试
def mutate(t, pc, probchange=0.1):
    if random() < probchange:
        return makerandomtree(pc)
    else:
        result = deepcopy(t)
        if isinstance(t, node):
            result.children = [mutate(c, pc, probchange) for c in t.children]
        return result


# 交叉与配对
# 从众多程序中选出两个表现优异者,并将其组合在一起构造出一个新的程序,通常的组合方式是用一棵树的分支
# 取代另一棵树的分支
# 执行交叉操作的函数以两棵树作为输入,并同时开始向下遍历.当到达某个随机选定的阈值时,
# 该函数便会返回前一棵树的一份拷贝,树上的某个分支会被后一棵树一的一个分支所取代。
# 通过同时对两棵树的即时遍历,函数会在每棵树上大致位于相同层次的节点处实施交叉操作
def crossover(t1, t2, probswap=0.7, top=1):
    if random() < probswap and not top:
        return deepcopy(t2)
    else:
        result = deepcopy(t1)
        if isinstance(t1, node) and isinstance(t2, node):
            result.children = [crossover(c, choice(t2.children), probswap, 0) for c in t1.children]
        return result


# 有了度量程序优劣的办法和修改最优程序的两种方法,我们现在可以构筑供程序进化用的竞争环境
def evolve(pc, popsize, rankfunction, maxgen=500, mutationrate=0.1, breedingrate=0.4, pexp=0.7, pnew=0.05):
    # 返回一个随机数,通常是一个较小的数
    # pexp的取值越小,我们得到的随机数就越小
    def selectindex():
        return int(log(random()) / log(pexp))

    # 创建一个随机的初始种群
    population = [makerandomtree(pc) for i in range(popsize)]
    for i in range(maxgen):
        scores = rankfunction(population)
        print
        scores[0][0]
        if scores[0][0] == 0: break

        # 总能得到两个最优的程序
        newpop = [scores[0][1], scores[1][1]]

        # 构造下一代
        while len(newpop) < popsize:
            if random() > pnew:
                newpop.append(mutate(
                    crossover(scores[selectindex()][1],
                              scores[selectindex()][1],
                              probswap=breedingrate),
                    pc, probchange=mutationrate))
            else:
                # 加入一个随机节点,以增加种群的多样性
                newpop.append(makerandomtree(pc))

        population = newpop
    scores[0][1].display()
    return scores[0][1]


# 返回一个针对给定数据集的排序函数
def getrankfunction(dataset):
    def rankfunction(population):
        scores = [(scorefunction(t, dataset), t) for t in population]
        scores.sort()
        return scores

    return rankfunction
